home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_09_06 / 9n06067a < prev    next >
Text File  |  1990-11-10  |  4KB  |  139 lines
  1.  
  2. /* Program by Bruce Terry
  3.    Written 04/14/1989
  4.    Revised 11/02/1990
  5.    Program designed to illustrate the technique of optimizing a binary tree
  6.    without using AVL or similar algorithims.
  7.    Designed for the Microsoft C 6.0 compiler.
  8.    Compatible with Microsoft QuickC 2.x
  9. */
  10.  
  11. #include <stdio.h>
  12. #include <stdlib.h>
  13. #include <malloc.h>
  14. #include <conio.h>
  15. #include <graph.h>
  16. #include <bios.h>
  17.  
  18. /* Global structs */
  19. typedef struct tnode {          /* Standard binary tree node */
  20.   /* Must put left and right child node pointers first */
  21.   struct tnode *left, *right;
  22.   int num;
  23. } TREENODE;
  24.  
  25. /* Function prototypes */
  26. TREENODE *addnode(TREENODE *, int);     /* Add to tree                      */
  27.  
  28. int getnum(void);                       /* Get a number for action          */
  29.  
  30. void keypause(void),                    /* Allow for pause                  */
  31.      main(void);                        /* Declaration of main              */
  32.  
  33. extern
  34. void *optimize(void *);                 /* Optimize a tree                  */
  35.  
  36. extern
  37. void printtree(TREENODE *),             /* Print contents of tree           */
  38.      showtree(TREENODE *, int, int);    /* Draw the tree                    */
  39.  
  40.  
  41. void main()
  42. {
  43.   int num,                      /* Number stored in tree */
  44.       choice;                   /* Menu choice           */
  45.   TREENODE *root = NULL;        /* Root of tree          */
  46.  
  47.   do {
  48.     _clearscreen(_GCLEARSCREEN);
  49.     puts("1)Add to tree\n2)Optimize tree\n3)Print tree\n4)Draw tree\n5)End");
  50.     switch(choice = getch()) {
  51.  
  52.       case '1':                 /* Add number to tree */
  53.         num = getnum();
  54.         root = addnode(root, num);
  55.         break;
  56.  
  57.       case '2':                 /* Optimize the tree */
  58.         root = (TREENODE *) optimize((void *) root);
  59.         break;
  60.  
  61.       case '3':                 /* Print contents of tree */
  62.         _clearscreen(_GCLEARSCREEN);
  63.         _settextposition(1, 1);
  64.         puts("Nodes of binary tree in numerical order\n\n");
  65.         printtree(root);
  66.         keypause();
  67.         break;
  68.  
  69.       case '4':                 /* Draw tree in 640 x 200 CGA screen */
  70.         _setvideomode(_HRESBW);
  71.         _clearscreen(_GCLEARSCREEN);
  72.         _moveto(333, 6);
  73.         showtree(root, 2, 40);
  74.         _settextposition(24, 1);
  75.         keypause();
  76.         _setvideomode(_DEFAULTMODE);
  77.         break;
  78.     }
  79.   } while (choice != '5');
  80.   _clearscreen(_GCLEARSCREEN);
  81.   puts("Program terminated.\n");
  82. }
  83.  
  84.  
  85. /* Function to retrieve an integer value that will be stored in the tree.
  86.    Usage:  int getnum(void);
  87.    Returns:  The number given.
  88. */
  89. int getnum()
  90. {
  91.   int number;   /* The number entered      */
  92.   _clearscreen(_GCLEARSCREEN);
  93.   do {
  94.     while (_bios_keybrd(_KEYBRD_READY))
  95.       _bios_keybrd(_KEYBRD_READ);
  96.     fputs("Enter an integer for storage: ", stdout);
  97.   } while (scanf("%d", &number) == 0);
  98.   return(number);
  99. }
  100.  
  101.  
  102. /* Recursive function to add an integer to the binary tree.
  103.    Usage:  TREENODE *addnode(node, number)
  104.              TREENODE *node;    /* Pointer to a local root
  105.              int number;        /* Number to add
  106.    Returns:  A pointer to the updated local root.
  107. */
  108. TREENODE *addnode(node, number)
  109.   TREENODE *node;
  110.   int number;
  111. {
  112.   if (node == NULL) {
  113.     if ((node = ((TREENODE *) malloc(sizeof(TREENODE)))) == NULL) {
  114.       fputs("Error in allocation\n", stderr);
  115.       exit(1);
  116.     }
  117.     node->num = number;
  118.     node->left = node->right = NULL;
  119.   }
  120.   else
  121.     if (number < node->num)
  122.       node->left = addnode(node->left, number);
  123.     else
  124.       if (number > node->num)
  125.         node->right = addnode(node->right, number);
  126.   return(node);
  127. }
  128.  
  129.  
  130. /* Function to display a prompt and wait for a response.
  131.    Usage:  void keypause(void);
  132.    Returns:  Nothing
  133. */
  134. void keypause()
  135. {
  136.   puts("Press a key to continue...");
  137.   _bios_keybrd(_KEYBRD_READ);
  138. }
  139.